import org.junit.Test;

public class Solution69 {
    /**
     * x 的平方根
     */
    public int mySqrt(int x) {
        if (x <= 1) return x;
        long l = 0, r = x;
        while (l <= r) {
            long mid = l + (r - l >> 1);
            if (mid * mid < x) {
                l = mid + 1;
            }else if (mid * mid > x){
                r = mid - 1;
            }else {
                return (int) mid;
            }
        }
        return (int) l - 1;
    }

    @Test
    public void test(){
        System.out.println(mySqrt(8));
    }
}
